//C07:PriorityQueue7.cpp
// A priority queue that will hand you a vector.
#include <algorithm>
#include <cstdlib>
#include <iostream>
#include <iterator>
#include <queue>
#include <vector>
using namespace std;

template<class T, class Compare>
class PQV
{
    vector<T> v;
    Compare comp;
    public:
        // Don't need to call make_heap(): it's empty:
        PQV(Compare cmp = Compare()) : comp(cmp){}
        void push(const T& x)
        {
            v.push_back(x);    // Put it at the end
            // Re-adjust the heap:
            push_heap(v.begin(), v.end(), comp);
        }

        void pop()
        {
            // Move the top element to the last position:
            pop_heap(v.begin(), v.end(), comp);
            v.pop_back();    // Remove that element
        }

        const T& top() { return v.front(); }
        bool empty() const { return v.empty(); }
        int size() const { return v.size(); }
        typedef vector<T> TVec;
        TVec getVector()
        {
            TVec r(v.begin(), v.end());
            // It's already a heap
            sort_heap(r.begin(), r.end(), comp);
            // Put it into priority-queue order:
            reverse(r.begin(), r.end());
            return r;
        }
};

int main(void)
{
    PQV<int, less<int>> pqi;
    srand(time(0));
    for (int i = 0; i < 100; i++)
    {
        pqi.push(rand() % 25);
    }
    const vector<int>& v = pqi.getVector();
    copy(v.begin(), v.end(),
        ostream_iterator<int>(cout, " "));
    cout << "\n-----------" << endl;
    while (!pqi.empty())
    {
        cout << pqi.top() << ' ';
        pqi.pop();
    }    


}